package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/13 15:13
 * https://leetcode-cn.com/problems/delete-operation-for-two-strings/
 */
public class Title583 {

    /**
     * 相当于求最长公共子序列的长度
     * dp[i][j]：表示[0,i-1]的字符串A和[0,j-1]的字符串B的最大公共子序列长度为dp[i][j]
     * 递推公式： word1.chatAt(i-1) == word2.charAt(j-1) dp[i][j] = d[i-1][j-1] + 1
     *            else     dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j])
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        int max = 0;
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <=word2.length() ; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
                if (dp[i][j] > max) {
                    max = dp[i][j];
                }
            }
        }
        return word1.length() + word2.length() - max;
    }

    /**
     * dp[i]表示[0 - i-1]的A和[0 - j-1]的B相同时所需最小的步数
     * 递推公式：
     *                  word1.charAt(i-1) == word2.charAt(i-2)  dp[i][j] = dp[i-1][j-1]
     *                  不相等：  删除A dp[i][j] = dp[i-1][j] + 1
     *                            删除B dp[i][j] = dp[i][j-1] + 1
     *                            删除AB dp[i][j] = dp[i-1][j-1] + 2
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance1(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        //初始化
        for (int i = 0; i < word1.length(); i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j < word2.length(); j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <=word2.length() ; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]) + 1, dp[i - 1][j - 1] + 2);
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }






    public static void main(String[] args) {

    }
}
